package com.leetcode.Offer;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class JZ38_2 {
    public String[] permutation(String s) {
        //全排列,结果存入HashSet中，自动去重
        boolean[] ifShow = new boolean[s.length()];
        Set<String> strings = new HashSet<>();

        dfs(s, strings, new StringBuilder(), ifShow);
        String[] strings1 = new String[strings.size()];

        int tmp = 0;
        for (String string : strings) {
            strings1[tmp++] = string;
        }
        return strings1;

    }

    private void dfs(String s, Set<String> strings, StringBuilder sb, boolean[] ifShow) {
        if (sb.length() == s.length()) {
            strings.add(sb.toString());
        }

        for (int i = 0; i < s.length(); i++) {
            if (!ifShow[i]) {
                sb.append(s.charAt(i));
                ifShow[i] = true;
                dfs(s, strings, sb, ifShow);
                sb = sb.deleteCharAt(sb.length() - 1);
                ifShow[i] = false;
            }

        }
    }

    public static void main(String[] args) {
        for (String abc : new JZ38_2().permutation("aab")) {
            System.out.println(abc);
        }
    }
}
